#pragma once

#include <algorithm>
#include <utility>
#include <vector>

namespace solution_047
{

class Solution
{
public:
    std::vector<std::vector<int>> permuteUnique(const std::vector<int>& nums) {
        auto permutations = std::vector{ { nums } };

        while (true) {
            permutations.push_back(permutations.back());
            next_permutation(permutations.back());
            if (permutations.back() == permutations.front()) {
                permutations.pop_back();
                break;
            }
        }

        return permutations;
    }

    std::vector<std::vector<int>> permuteUniqueSTL(const std::vector<int>& nums) {
        auto permutations = std::vector{ { nums } };

        while (true) {
            permutations.push_back(permutations.back());
            std::next_permutation(permutations.back().begin(), permutations.back().end());
            if (permutations.back() == permutations.front()) {
                permutations.pop_back();
                break;
            }
        }

        return permutations;
    }

private:
    void next_permutation(std::vector<int>& nums) noexcept {
        switch (nums.size()) {
            case 2: std::swap(nums.front(), nums.back());
            case 0:
            case 1: break;
            default: {
                int l = nums.size() - 2;
                int r = nums.size() - 1;
                while (l >= 0 && nums.at(l) >= nums.at(r)) {
                    --l;
                    --r;
                }
                if (l >= 0) {
                    while (r < (int)nums.size() - 1 && nums.at(r + 1) > nums.at(l))
                        ++r;
                    std::swap(nums.at(l), nums.at(r));
                }
                ++l;
                r = nums.size() - 1;
                while (l < r) {
                    std::swap(nums.at(l), nums.at(r));
                    ++l;
                    --r;
                }
            }
        }
    }
};

}  /* namespace solution_047 */
